package com.leetcodehot.problems;

import java.util.Arrays;

public class problems2389 {
    /**
     * 给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
     * <p>
     * 返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。
     * <p>
     * 子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
     */
    public int[] answerQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int m = queries.length;
        int[] ans = new int[m];
        Arrays.sort(nums);
        int[] sum = new int[n];
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        for (int idx = 0; idx < m; idx++) {
            int left = -1;
            int right = n;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (sum[mid] <= queries[idx]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }//left
            ans[idx] = left + 1;
        }
        return ans;
    }
}
